"""

"""


class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        # 统计数组中每个数字出现的次数
        count = {}
        for num in arr:
            if num in count:
                count[num] += 1
            else:
                count[num] = 1

        # 按照出现次数排序
        count_list = sorted(count.values(), reverse=True)
        print(type(count_list))
        print(count_list)

        # 计算删除次数
        delete_count = 0
        total_count = len(arr)
        half_count = total_count // 2
        for i in range(len(count_list)):
            delete_count += count_list[i]
            if delete_count >= half_count:
                return i+1
        return len(count_list)


if __name__ == '__main__':
    arr = [3,3,3,3,5,5,5,2,2,7]
    solution = Solution()
    result = solution.minSetSize(arr)